from typing import List


class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        # 排序cuts并添加左右端点
        cuts.sort()
        cuts = [0] + cuts + [n]

        size = len(cuts)

        # 定义状态矩阵：dp[i][j] = 以i和j为端点的最小值
        dp = [[float("inf")] * size for _ in range(size)]

        for i in range(size - 1, -1, -1):
            for j in range(i, size):
                if i == j or i + 1 == j:
                    dp[i][j] = 0
                for k in range(i + 1, j):
                    dp[i][j] = min(dp[i][j], cuts[j] - cuts[i] + dp[i][k] + dp[k][j])

        return dp[0][-1]


if __name__ == "__main__":
    print(Solution().minCost(n=7, cuts=[1, 3, 4, 5]))  # 16
    print(Solution().minCost(n=9, cuts=[5, 6, 1, 4, 2]))  # 22
